// 您需要在二叉树的每一行中找到最大的值。

// 示例：

// 输入: 

//           1
//          / \
//         3   2
//        / \   \  
//       5   3   9 

// 输出: [1, 3, 9]
// 通过次数15,611提交次数25,514

#include <vector>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (root == nullptr) return {};
        vector<int> res{};
        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            int maxVal{INT_MIN};
            int n = q.size();
            while (n--) {
                TreeNode* node = q.front();
                q.pop();
                if (node->val > maxVal) maxVal = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(maxVal);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if (nullptr == root) {
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            int maxVal = INT_MIN;
            for (int i = 0; i < n; ++i) {
                TreeNode* node = q.front();
                q.pop();
                maxVal = max(maxVal, node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.emplace_back(maxVal);
        }
        return res;
    }
};
